package cn.edu.besti.cs2023.W2321;

public class Searching_Maru {

    /*线性查找*/
    public int linearSearch(int[] data, int target)/*有哨兵类*/ {
        int j = 1;
        data[0] = target;
        for (int i = data.length - 1; data[i] != target; i--) {
            j = i;
        }
        return j - 1;
    }

    public boolean linearSearchNone(int[] data, int target)/*无哨兵类*/ {
        boolean result = false;
        for (int i = 0; i < data.length; i++) {
            if (data[i] == target) {
                result = true;
            }
        }
        return result;
    }

    /*二分查找*/
    public boolean binarySearch(int[] data, int target) {
        int low = 0, mid, high = data.length - 1;
        while (low <= high) {
            mid = (low + high) / 2;
            if (data[mid] == target) {
                return true;
            } else if (data[mid] > target) {
                high = mid - 1;
            } else
                low = mid + 1;
        }
        return false;
    }

    /*插值查找*/
    public boolean insertionSearch(int[] data, int target, int low, int high) {
        int mid = low + (target - data[low]) / (data[high] - data[low]) * (high - low);
        if (target<low||target>high)
            return false;
        if (data[mid] == target) {
            return true;
        } else if (data[mid] > target) {
            if(mid>=low&&mid<=high)
            return insertionSearch(data, target, low, mid - 1);
            else
                return false;
        } else
            if(mid>=low&&mid<=high)
            return insertionSearch(data, target, mid + 1, high);
            else
                return false;

    }

    /*斐波那契查找*/
    public int Fibonacci(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }
    public boolean fibonacciSearch(int[] data, int target){
        int n=data.length-1;
        int low = 1, high = n, mid;
        int k = 0;
        while (n > Fibonacci(k) - 1) {
            k++;
        }
        int[] temp = new int[Fibonacci(k)];
        System.arraycopy(data, 0, temp, 0, data.length);
        for (int i = n + 1; i <= Fibonacci(k) - 1; i++) {
            temp[i] = temp[n];
        }

        while (low <= high) {
            mid = low + Fibonacci(k - 1) - 1;
            if (temp[mid] > target) {
                high = mid - 1;
                k = k - 1;
            } else if (temp[mid] < target) {
                low = mid + 1;
                k = k - 2;
            } else {
                if (mid <= n) {
                    return true;
                } else {
                    return false;
                }
            }
        }
        return false;

    }


    /*树表查找*/
//BTS查找我另外设置一个大类

    /*分块查找*/
//BTS查找我另外设置一个大类

    /*哈希查找*/
//HashSearch查找我另外设置一个大类

}

